#include <mpi.h>
#include <stdio.h>
#include <unistd.h>
#include <cmath>

#define PRINTR(format,...) \
if (rank==0) printf(format,##__VA_ARGS__)

#define PRINTI(format,...) \
printf("Proc#%d:\t" format,rank,##__VA_ARGS__)

bool in_level(int node_id, int level){
    return (1<<level)-1 <= node_id && (1<<(level+1))-2 >= node_id;
}

int main(int argc, char** argv){
    int rank, nproc;
    int TAG = 100;
    MPI_Request send_request, recv_request;
    MPI_Status send_status, recv_status;
    MPI_Init(&argc, &argv);
    MPI_Comm_size(MPI_COMM_WORLD, &nproc);
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);
    
    int data = rank+1;

    int height = floor(log2(nproc))+1;
    for (int level = height-1; level > 0; level--){
        if (in_level(rank,level)){
            int parent = (rank-1) >> 1;
            MPI_Send(&data, 1, MPI_INT, parent, TAG, MPI_COMM_WORLD);
        }
        else if (in_level(rank,level-1)){
            int temp;
            int child = (rank<<1)+1;
            if (child < nproc){
                MPI_Recv(&temp,1,MPI_INT,child,TAG,MPI_COMM_WORLD,&recv_status);
                data+=temp;
            }
            child++;
            if (child < nproc){
                MPI_Recv(&temp,1,MPI_INT,child,TAG,MPI_COMM_WORLD,&recv_status);
                data+=temp;
            }
        }
    }
    for (int level = 1; level<height; level++){
        if (in_level(rank,level)){
            int parent = (rank-1)>>1;
            MPI_Recv(&data,1,MPI_INT,parent,TAG,MPI_COMM_WORLD,&recv_status);
        }
        else if (in_level(rank,level-1)){
            int child = (rank<<1)+1;
            if (child < nproc){
                MPI_Send(&data,1,MPI_INT,child,TAG,MPI_COMM_WORLD);
            }
            child++;
            if (child < nproc){
                MPI_Send(&data,1,MPI_INT,child,TAG,MPI_COMM_WORLD);
            }
        }
    }
    PRINTI("data=%d\n",data);

    MPI_Finalize();
}